package leetcode_1000;

import java.util.Arrays;

/**
 * @author 周杨
 * 2018年11月20日 下午6:15:50 能否把一个二进制数组分成三个连续子数组 每个子数组里的数相等 二进制数可以保留前导0
 * ThreeEqualParts_927.java
 * description:扫描问题 判断1的个数 然后比较各个数组是否相等 再判断后导0是否足够多 AC 79%
 */
public class ThreeEqualParts_927 {
	public int[] threeEqualParts(int[] A) {
		int[] IMP = new int[]{-1, -1};
        int N = A.length;
        int S = 0;
        for (int x: A) S += x;
        if (S % 3 != 0) return IMP;//如果1的个数不是3的倍数 那么是错的
        int T = S / 3;
        if (T == 0) return new int[]{0, N - 1};
        int i1 = -1, j1 = -1, i2 = -1, j2 = -1, i3 = -1, j3 = -1;
        int su = 0;
        for (int i = 0; i < N; ++i) {
            if (A[i] == 1) {//切割数组
                su += 1;
                if (su == 1) i1 = i;
                if (su == T) j1 = i;
                if (su == T+1) i2 = i;
                if (su == 2*T) j2 = i;
                if (su == 2*T + 1) i3 = i;
                if (su == 3*T) j3 = i;
            }
        }
        int[] part1 = Arrays.copyOfRange(A, i1, j1+1);
        int[] part2 = Arrays.copyOfRange(A, i2, j2+1);
        int[] part3 = Arrays.copyOfRange(A, i3, j3+1);
        if (!Arrays.equals(part1, part2)) return IMP;
        if (!Arrays.equals(part1, part3)) return IMP;
        int x = i2 - j1 - 1;
        int y = i3 - j2 - 1;
        int z = A.length - j3 - 1;
        if (x < z || y < z) return IMP;//判断后导0是否足够多
        return new int[]{j1+z, j2+z+1};
    }
}
